package 栈;

import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/score-of-parentheses/
 * <p>
 * 给定一个平衡括号字符串S，按下述规则计算该字符串的分数：
 * <p>
 * ()  得 1 分。
 * AB  得A + B分，其中 A 和 B 是平衡括号字符串。
 * (A) 得2 * A分，其中 A 是平衡括号字符串。
 * <p>
 * 字符串 S 中的每一个位置都有一个“深度”，即该位置外侧嵌套的括号数目。例如，字符串 (()(.())) 中的 . 的深度为 2，
 * 因为它外侧嵌套了 2 层括号：(__(.__))。
 * <p>
 * 我们用一个栈来维护当前所在的深度，以及每一层深度的得分。
 * 当我们遇到一个左括号 ( 时，我们将深度加一，并且新的深度的得分置为 0。当我们遇到一个右括号 ) 时，
 * 我们将当前深度的得分乘二并加到上一层的深度。这里有一种例外情况，如果遇到的是 ()，那么只将得分加一。
 */
public class _856_括号的分数 {

    public static void main(String[] args) {
        System.out.println(scoreOfParentheses("(()(()))"));
    }

    // (()(()))
    public static int scoreOfParentheses(String s) {
        Stack<Integer> stack = new Stack();
        stack.push(0); // The score of the current frame

        for (char c : s.toCharArray()) {
            if (c == '(')
                stack.push(0);
            else {
                int v = stack.pop();
                int w = stack.pop();
                stack.push(w + Math.max(2 * v, 1));
            }
        }
        return stack.pop();
    }

    // (()(()))
    // (() len=1 ans =2
    // (()(() len=3 ans=6
    public static int scoreOfParentheses2(String s) {
        int ans = 0, len = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '(') {
                len++;
            } else {
                len--;
                if (s.charAt(i - 1) == '(') {
                    ans += 1 << len;
                }
            }
        }
        return ans;
    }

}
